GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Metropolis-Algorithmus</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Metropolis-Algorithmus</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Metropolis-Algorithmus</b> ist ein <a href="MCMC" class="mw-redirect" title="MCMC">Markov-Chain-Monte-Carlo-Verfahren</a> (MCMC) zur Erzeugung von Zuständen eines Systems entsprechend der <a href="Boltzmann-Statistik" title="Boltzmann-Statistik">Boltzmann-Verteilung</a>. Der davon abgeleitete, allgemeinere <b>Metropolis-Hastings-Algorithmus</b><sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> ermöglicht es, Folgen von <a href="Zufallsvariable" title="Zufallsvariable">Zufallsvariablen</a>, genauer <a href="Markow-Kette" title="Markow-Kette">Markow-Ketten</a>, zu simulieren, die eine gewünschte Verteilung als <a href="Station%C3%A4re_Verteilung" title="Stationäre Verteilung">stationäre Verteilung</a> besitzen, insbesondere in vielen Fällen, bei denen die Verteilungen der Zufallsvariablen nicht direkt simuliert werden können.

</p>

<div class="mw-heading mw-heading2"><h2 id="Metropolis-Algorithmus">Metropolis-Algorithmus</h2></div>

<p>Der <i>Metropolis-Algorithmus</i> wurde 1953 von <a href="Nicholas_Metropolis" title="Nicholas Metropolis">Nicholas Metropolis</a>, <a href="Marshall_Rosenbluth" title="Marshall Rosenbluth">Marshall Rosenbluth</a>, <a href="Edward_Teller" title="Edward Teller">Edward Teller</a>, <a href="Augusta_H._Teller" title="Augusta H. Teller">Augusta H. Teller</a>, <a href="Arianna_W._Rosenbluth" title="Arianna W. Rosenbluth">Arianna W. Rosenbluth</a> publiziert<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> (zur Geschichte siehe auch <i><a href="Monte-Carlo-Simulation" title="Monte-Carlo-Simulation">Monte-Carlo-Simulation</a></i>). Er wird dazu genutzt, eine <a href="Markow-Kette" title="Markow-Kette">Markow-Kette</a> und damit die Zustände eines Systems entsprechend der Boltzmann-Verteilung zu erzeugen. Dabei hängt der neue Zustand des Systems <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i+1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i+1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bc56fe176df2317239339ad413c58d09cd1c187b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.23ex; height:2.009ex;" alt="{\displaystyle x_{i+1}}" loading="lazy"></span> nur vom vorherigen Zustand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span> ab.

</p><p>Im Folgenden wird der <a href="Algorithmus" title="Algorithmus">Algorithmus</a> für den Fall beschrieben, dass das System von einem mehrdimensionalen Ort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db2dc6ced9cc3bc7e8b9f2707cbec033f6d3759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.343ex;" alt="{\displaystyle {\vec {x}}}" loading="lazy"></span> abhängt. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db2dc6ced9cc3bc7e8b9f2707cbec033f6d3759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.343ex;" alt="{\displaystyle {\vec {x}}}" loading="lazy"></span> sei kontinuierlich und der aktuelle Ort nach <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> Iterationen wird mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}_{i}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97dc64e456d28b08c449ec343111cc5c3ce39f72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.676ex;" alt="{\displaystyle {\vec {x}}_{i}}" loading="lazy"></span> bezeichnet. Der Metropolis-Algorithmus ergibt sich dann durch Wiederholung der folgenden Schritte:

</p>

<ol><li>Ein neuer Ort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}={\vec {x}}_{i}+r\cdot {\vec {q}}}">

<mover>

</mover>

</mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}={\vec {x}}_{i}+r\cdot {\vec {q}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/431629bc851b323e215b0fc7e77afd75626831bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.369ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}={\vec {x}}_{i}+r\cdot {\vec {q}}}" loading="lazy"></span> wird ausgewählt, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {q}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {q}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a4e063f8ee7dae2488859c45a4e645db5148085.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.309ex; height:2.676ex;" alt="{\displaystyle {\vec {q}}}" loading="lazy"></span> ein <a href="Zufallsvektor" title="Zufallsvektor">Zufallsvektor</a> aus Komponenten zwischen −1 und +1 und <i>r</i> ein fest gewählter Suchradius ist, das heißt, der neue Ortsvektor wird als Zufallsvektor in einer festen Umgebung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}_{i}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97dc64e456d28b08c449ec343111cc5c3ce39f72.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.676ex;" alt="{\displaystyle {\vec {x}}_{i}}" loading="lazy"></span> gewählt, wobei die verschiedenen Komponenten der räumlichen Dimensionen nicht notwendigerweise gleich sein müssen.</li>

<li>Die Energie-Differenz <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Delta E:=E\left({\vec {y}}\right)-E\left({\vec {x}}_{i}\right)}">

<mrow>

<mover>

</mover>

</mrow>

</mrow>

<mrow>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta E:=E\left({\vec {y}}\right)-E\left({\vec {x}}_{i}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3ae173a8470e36c90d93e348f621cf3d515a629e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.635ex; height:2.843ex;" alt="{\displaystyle \Delta E:=E\left({\vec {y}}\right)-E\left({\vec {x}}_{i}\right)}" loading="lazy"></span> wird berechnet und die neue Konfiguration mit der <a href="Wahrscheinlichkeit" title="Wahrscheinlichkeit">Wahrscheinlichkeit</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle p_{\mathrm {A} }=\min \left(1,\exp \left(-{\frac {\Delta E}{kT}}\right)\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle p_{\mathrm {A} }=\min \left(1,\exp \left(-{\frac {\Delta E}{kT}}\right)\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf82b04871f563784fc8a35573f21b69fa05a47e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; margin-left: -0.089ex; width:26.653ex; height:4.843ex;" alt="{\displaystyle \textstyle p_{\mathrm {A} }=\min \left(1,\exp \left(-{\frac {\Delta E}{kT}}\right)\right)}" loading="lazy"></span> akzeptiert, wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> für die <i>Temperatur</i> des Systems und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> für die <a href="Boltzmann-Konstante" title="Boltzmann-Konstante">Boltzmann-Konstante</a> steht.<br>Dies bedeutet:

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta E\leq 0\,}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c95f4dfdd292799bc8143fa2b50affa818a9df0a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:8.36ex; height:2.343ex;" alt="{\displaystyle \Delta E\leq 0\,}" loading="lazy"></span>, die neue Position also energetisch gleichwertig oder günstiger, wird <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f0c914c24b65c8c8b48ddbc6acbc092d5458c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.264ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}}" loading="lazy"></span> in jedem Fall als neuer aktueller Ort akzeptiert, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}_{i+1}={\vec {y}}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}_{i+1}={\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/30f03be631ad598c2e6a57668fdcdd68f159f1b8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.593ex; height:2.676ex;" alt="{\displaystyle {\vec {x}}_{i+1}={\vec {y}}}" loading="lazy"></span>.</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Delta E>0\,}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f3a4620a648c5a1624a8582fe1004f685d1603c4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.36ex; height:2.176ex;" alt="{\displaystyle \Delta E>0\,}" loading="lazy"></span>, die neue Position also energetisch ungünstiger, wird <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f0c914c24b65c8c8b48ddbc6acbc092d5458c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.264ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}}" loading="lazy"></span> dagegen nur mit der Wahrscheinlichkeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\mathrm {A} }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\mathrm {A} }}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/90b20c9dd9b4f36f83c1ba46131cd27706b0eae5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.724ex; height:2.009ex;" alt="{\displaystyle p_{\mathrm {A} }}" loading="lazy"></span> als neuer aktueller Ort akzeptiert, wozu man praktisch eine <a href="Zufallszahl" title="Zufallszahl">Zufallszahl</a> <i>q</i> zwischen 0 und 1 bestimmt und anschließend mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\mathrm {A} }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\mathrm {A} }}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/90b20c9dd9b4f36f83c1ba46131cd27706b0eae5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.724ex; height:2.009ex;" alt="{\displaystyle p_{\mathrm {A} }}" loading="lazy"></span> vergleicht: Ist <i>q</i> kleiner als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\mathrm {A} }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\mathrm {A} }}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/90b20c9dd9b4f36f83c1ba46131cd27706b0eae5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.724ex; height:2.009ex;" alt="{\displaystyle p_{\mathrm {A} }}" loading="lazy"></span>, wird <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f0c914c24b65c8c8b48ddbc6acbc092d5458c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.264ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}}" loading="lazy"></span> als neuer aktueller Ort akzeptiert, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}_{i+1}={\vec {y}},}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}_{i+1}={\vec {y}},}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7c0b47b1d55e54dbbdac38cfaf8eb0426d6cae3a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.24ex; height:2.676ex;" alt="{\displaystyle {\vec {x}}_{i+1}={\vec {y}},}" loading="lazy"></span> andernfalls nicht, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}_{i+1}={\vec {x}}_{i}}">

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

<msub>

<mover>

</mover>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}_{i+1}={\vec {x}}_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/93176958f89de2100d21c10d82f295b34f4d454a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.458ex; height:2.676ex;" alt="{\displaystyle {\vec {x}}_{i+1}={\vec {x}}_{i}}" loading="lazy"></span>.</li></ul></li></ol>

<p>Das oben beschriebene Verfahren lässt sich einfach auch auf andere Fälle wie beispielsweise diskrete Zustände übertragen. Für Systeme aus vielen wechselwirkenden Teilchen wird der Metropolis-Algorithmus dabei zunächst <i>lokal</i> für ein einzelnes Teilchen angewandt und anschließend – entweder nacheinander oder zufällig – auf alle Teilchen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Autokorrelation">Autokorrelation</h3></div>

<p>Kleine Werte für die Vorschlagsänderungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |r|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |r|}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/33724ed2b4730b9b29dd9d08e8b216c539ed7dde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.342ex; height:2.843ex;" alt="{\displaystyle |r|}" loading="lazy"></span> führen dabei zu großen Akzeptanzraten, haben jedoch den Nachteil hoher <a href="Autokorrelation" title="Autokorrelation">Autokorrelationszeiten</a>

</p>

</mrow>

</mrow>

</munderover>

</mrow>

</mrow>

</munderover>

<mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \tau =\sum _{i=0}^{\infty }\Gamma (i)=\sum _{i=0}^{\infty }\left\langle \left(A_{0}-\langle A\rangle \right)\left(A_{i}-\langle A\rangle \right)\right\rangle }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/04e48cba4535dca49ab78cac60cc404768bcc5d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:42.888ex; height:6.843ex;" alt="{\displaystyle \tau =\sum _{i=0}^{\infty }\Gamma (i)=\sum _{i=0}^{\infty }\left\langle \left(A_{0}-\langle A\rangle \right)\left(A_{i}-\langle A\rangle \right)\right\rangle }" loading="lazy"></span></dd></dl>

<p>Große Werte von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |r|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |r|}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/33724ed2b4730b9b29dd9d08e8b216c539ed7dde.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.342ex; height:2.843ex;" alt="{\displaystyle |r|}" loading="lazy"></span> dagegen verkürzen zwar die Autokorrelationszeit, haben dafür aber nun den Nachteil einer geringeren Akzeptanzrate, so dass in der Praxis stets ein Mittelweg gesucht werden muss.

</p>

<div class="mw-heading mw-heading3"><h3 id="Burn-In_Phase">Burn-In Phase</h3></div>

<p>Da die Markovkette an einem beliebigen Punkt startet, welcher eventuell sehr unwahrscheinlich ist, sind die anfänglich vorgeschlagenen Zustände aufgrund der Autokorrelation immer noch unwahrscheinlich. Erst nach einer gewissen Zahl an akzeptierten Vorschlägen erreicht das Verfahren Zustände, welche „<a href="Repr%C3%A4sentativit%C3%A4t" title="Repräsentativität">repräsentative</a>“ Stichproben aus der stationären Verteilung sind. Daher werden anfänglich gezogene Stichproben verbrannt, sie stammen aus der „Burn-In Phase“. Zur Diagnostik der Konvergenz von Markovketten, kann z. B. die <a href="Gelman-Rubin-Statistik" title="Gelman-Rubin-Statistik">Gelman-Rubin Diagnostik</a> durchgeführt werden, bei der mehrere Markov-Ketten simuliert werden und durch Zusammenfassungsstatiken überprüft wird, ob diese Ketten zu ähnlichen Werten konvergiert sind.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> Während der Burn-In Phase unterscheiden sich die simulierten Markov-Ketten typischerweise deutlich in den Zusammenfassungsstatistiken.

</p>

<div class="mw-heading mw-heading2"><h2 id="Metropolis-Hastings-Algorithmus">Metropolis-Hastings-Algorithmus</h2></div>

<p>W. Keith Hastings generalisierte 1970 das Verfahren.<sup id="cite_ref-:0_1-1" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Der <i>Metropolis-Hastings-Algorithmus</i> kann Zustände für eine beliebige Wahrscheinlichkeitsverteilung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W({\vec {x}})}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W({\vec {x}})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a18cb6313d05c2d9a635b5d2328f7fe74e74c05.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.574ex; height:2.843ex;" alt="{\displaystyle W({\vec {x}})}" loading="lazy"></span> erzeugen. Voraussetzung ist lediglich, dass die Dichte an jedem Ort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db2dc6ced9cc3bc7e8b9f2707cbec033f6d3759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.343ex;" alt="{\displaystyle {\vec {x}}}" loading="lazy"></span> berechnet werden kann. Der Algorithmus benutzt eine <i>Vorschlagsdichte</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P({\vec {y}}\mid {\vec {x}})}">

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P({\vec {y}}\mid {\vec {x}})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0ad8ce54c9149656856180d6609e2f966a975053.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.086ex; height:2.843ex;" alt="{\displaystyle P({\vec {y}}\mid {\vec {x}})}" loading="lazy"></span>, die vom derzeitigen Ort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {x}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {x}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/db2dc6ced9cc3bc7e8b9f2707cbec033f6d3759c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:2.343ex;" alt="{\displaystyle {\vec {x}}}" loading="lazy"></span> und möglichem nächsten Ort <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f0c914c24b65c8c8b48ddbc6acbc092d5458c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.264ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}}" loading="lazy"></span> abhängt. Beim Metropolis-Hastings-Algorithmus wird ein Vorschlag <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\vec {y}}}">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\vec {y}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5f0c914c24b65c8c8b48ddbc6acbc092d5458c4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.264ex; height:2.676ex;" alt="{\displaystyle {\vec {y}}}" loading="lazy"></span> anhand der Vorschlagsdichte zufällig erzeugt und mit der Wahrscheinlichkeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{\mathrm {A} }=\min \left(1,{\frac {W({\vec {y}})P({\vec {x}}\mid {\vec {y}})}{W({\vec {x}})P({\vec {y}}\mid {\vec {x}})}}\right)}">

<msub>

</mrow>

</msub>

<mrow>

<mrow>

<mfrac>

<mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mrow>

<mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{\mathrm {A} }=\min \left(1,{\frac {W({\vec {y}})P({\vec {x}}\mid {\vec {y}})}{W({\vec {x}})P({\vec {y}}\mid {\vec {x}})}}\right)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/03a6e86679aa241b16c66e5ac49854f7b8dd8405.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; margin-left: -0.089ex; width:30.198ex; height:6.509ex;" alt="{\displaystyle p_{\mathrm {A} }=\min \left(1,{\frac {W({\vec {y}})P({\vec {x}}\mid {\vec {y}})}{W({\vec {x}})P({\vec {y}}\mid {\vec {x}})}}\right)}" loading="lazy"></span> akzeptiert.

</p><p>Für eine Vorschlagsdichte, die symmetrisch ist (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P({\vec {y}}\mid {\vec {x}})=P({\vec {x}}\mid {\vec {y}})}">

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P({\vec {y}}\mid {\vec {x}})=P({\vec {x}}\mid {\vec {y}})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/214ed4740a9bfed8fe69a98567c8888721cceb9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.271ex; height:2.843ex;" alt="{\displaystyle P({\vec {y}}\mid {\vec {x}})=P({\vec {x}}\mid {\vec {y}})}" loading="lazy"></span>), sowie eine Boltzmann-Verteilung als Wahrscheinlichkeitsverteilung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"></span> ergibt sich hieraus der ursprüngliche Metropolis-Algorithmus.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Monte-Carlo-Simulation">Monte-Carlo-Simulation</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Monte-Carlo-Simulation" title="Monte-Carlo-Simulation">Monte-Carlo-Simulation</a></i></div>

<p>Bei <i>Monte-Carlo-Simulationen</i> werden Konfigurationen mittels des Metropolis-Algorithmus erzeugt und Mittelwerte/Erwartungswerte physikalisch relevanter Größen berechnet, beispielsweise der Erwartungswert des Drucks oder der Dichte:

</p>

<mrow>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\langle A\right\rangle =Z^{-1}\int [\mathrm {d} x]e^{-\beta E(x)}\,A(x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf8f88d58d4daa532e09bd1b8566dd355693ce97.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:29.469ex; height:5.676ex;" alt="{\displaystyle \left\langle A\right\rangle =Z^{-1}\int [\mathrm {d} x]e^{-\beta E(x)}\,A(x)}" loading="lazy"></span></dd></dl>

<p>mit

</p>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z=\int [\mathrm {d} x]e^{-\beta E(x)}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0a52750edb73633701531069dc15c7b698dcb102.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:17.9ex; height:5.676ex;" alt="{\displaystyle Z=\int [\mathrm {d} x]e^{-\beta E(x)}}" loading="lazy"></span></dd>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \beta =(kT)^{-1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e063a2ea3123957b10eb4c0695d908b48cf68a61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.42ex; height:3.176ex;" alt="{\displaystyle \beta =(kT)^{-1}}" loading="lazy"></span></dd></dl>

<p>Dazu werden von den Iterationsschritten des Metropolis-Algorithmus zunächst so viele ausgeführt, bis sich das System hinreichend nah an das <a href="Thermisches_Gleichgewicht" class="mw-redirect" title="Thermisches Gleichgewicht">thermische Gleichgewicht</a> angenähert hat, d. h. bis die Wahrscheinlichkeit der einzelnen Konfigurationen der Boltzmann-Verteilung entspricht. Befindet sich das System im thermischen Gleichgewicht, so entspricht die Wahrscheinlichkeitsverteilung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W(x)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86ead36b42ec68c542b267f9e6bb62cf911a764b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.574ex; height:2.843ex;" alt="{\displaystyle W(x)}" loading="lazy"></span> der Boltzmann-Verteilung, d. h. die Konfigurationen werden mit der Wahrscheinlichkeit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W(x)={\frac {1}{Z}}e^{-\beta E(x)}}">

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W(x)={\frac {1}{Z}}e^{-\beta E(x)}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7fd5677c38b3a3b671d0157228dcb5d1b205f83e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:18.201ex; height:5.176ex;" alt="{\displaystyle W(x)={\frac {1}{Z}}e^{-\beta E(x)}}" loading="lazy"></span> erzeugt (<i><a href="Importance_Sampling" title="Importance Sampling">Importance Sampling</a></i>) und es muss lediglich über jeden <a href="Messwert" title="Messwert">Messwert</a>, bzw. Messwerte in konstantem Abstand, gemittelt werden: <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \left\langle A\right\rangle =\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}A(x_{i})}">

<mrow>

</mrow>

</mrow>

</munder>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left\langle A\right\rangle =\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}A(x_{i})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01ddc253636b08afbc0d311c0343365f920fa025.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:24.494ex; height:7.343ex;" alt="{\displaystyle \left\langle A\right\rangle =\lim _{N\to \infty }{\frac {1}{N}}\sum _{i=1}^{N}A(x_{i})}" loading="lazy"></span>.

</p><p>Der Metropolis-Algorithmus erzeugt Systeme im <a href="Kanonischer_Zustand" class="mw-redirect" title="Kanonischer Zustand">kanonischen Zustand</a>, d. h. mit konstanter Temperatur. Um <a href="Mikrokanonisches_Ensemble" title="Mikrokanonisches Ensemble">mikrokanonische Zustände</a> zu erzeugen, können Molekulardynamik-Algorithmen verwendet werden.

</p><p>In der Originalarbeit von Nicholas Metropolis et al. wurde der Algorithmus für die Monte-Carlo-Simulation eines zweidimensionalen Harte-Scheiben-Modells verwendet. Der Algorithmus wurde später für eine Vielzahl unterschiedlichster Monte-Carlo-Simulationen in Bereichen wie z. B. bei der <a href="Thermodynamik" title="Thermodynamik">Thermodynamik</a> bzw. der <a href="Statistische_Physik" title="Statistische Physik">Statistischen Physik</a>, <a href="Festk%C3%B6rperphysik" title="Festkörperphysik">Festkörperphysik</a>, <a href="Quantenelektrodynamik" title="Quantenelektrodynamik">Quantenelektrodynamik</a> oder <a href="Quantenchromodynamik" title="Quantenchromodynamik">Quantenchromodynamik</a> eingesetzt. Dabei muss der Algorithmus gegebenenfalls angepasst werden; beispielsweise muss man die Energie durch den <a href="Hamiltonoperator" title="Hamiltonoperator">Hamiltonoperator</a> oder die <a href="Wirkung_(Physik)" title="Wirkung (Physik)">Wirkung</a> ersetzen.

</p><p>Der Metropolis-Algorithmus ist leicht zu implementieren, jedoch nicht immer der effizienteste Algorithmus. Alternativ können andere lokale oder nicht-lokale Verfahren Verwendung finden.

</p>

<div class="mw-heading mw-heading3"><h3 id="Optimierungsverfahren">Optimierungsverfahren</h3></div>

<p>Der Metropolis-Algorithmus kann auch als stochastisches <a href="Optimierungsverfahren" class="mw-redirect" title="Optimierungsverfahren">Optimierungsverfahren</a> zum Finden eines <a href="Globales_Minimum" class="mw-redirect" title="Globales Minimum">globalen Minimums</a> einer <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktion</a> verwendet werden. Hierzu wird mit einer hohen Temperatur begonnen, damit möglichst ein großes Gebiet der Wertelandschaft besucht wird. Anschließend wird die Temperatur langsam abgesenkt, sodass man sich mit immer höherer Wahrscheinlichkeit einem <a href="Extremwert" title="Extremwert">Minimum</a> nähert. Ein solcher Metropolis-Algorithmus mit von der (Simulations-)Zeit abhängiger Temperatur heißt <a href="Simulierte_Abk%C3%BChlung" title="Simulierte Abkühlung">simulierte Abkühlung</a> (<i>simulated annealing</i>). Für bestimmte Formen der simulierten Abkühlung konnte bewiesen werden, dass sie das globale Minimum einer Wertelandschaft finden.

</p><p>Das Verfahren ähnelt dem <a href="Bergsteigeralgorithmus" title="Bergsteigeralgorithmus">Bergsteigeralgorithmus</a> (<i>hill climbing</i>), akzeptiert jedoch im Gegensatz zu diesem auch Schritte weg vom nächsten Minimum, so dass das „Hängen bleiben“ in lokalen Minima vermieden wird, die noch nicht das absolute Minimum ergeben. Der Metropolis-Algorithmus überwindet so kleine Hügel, bevor weiter in Richtung Tal gegangen wird, da der Anstieg in Richtung Hügel klein ist und somit die Akzeptanzwahrscheinlichkeit relativ groß ist.

</p>

<div class="mw-heading mw-heading3"><h3 id="Bayessches_Lernen">Bayessches Lernen</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Bayessches_Lernen" class="mw-redirect" title="Bayessches Lernen">Bayessches Lernen</a></i></div>

<p>Zum Ziehen von Stichproben (engl. Sample) aus der Posterior-Verteilung wird folgende Akzeptanzwahrscheinlichkeit verwendet, um von einem Zustand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta _{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta _{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/302b19204ed378e99ff4575341a67eebdbe5a555.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.89ex; height:2.509ex;" alt="{\displaystyle \theta _{i}}" loading="lazy"></span> zu einem vorgeschlagenen Zustand <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta ^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta ^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5c77b69ba747144843a16bb2e053e9fcd8583735.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.145ex; height:2.343ex;" alt="{\displaystyle \theta ^{*}}" loading="lazy"></span> überzugehen:

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

<mfrac>

<mrow>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/994636aa96438143b13da7f7efca6d0427634034.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.671ex; width:50.55ex; height:6.509ex;" alt="{\displaystyle P_{acc}(\theta _{i}\to \theta ^{*})=\min \left(1,{\frac {{\mathcal {L}}(y|\theta ^{*})P(\theta ^{*})}{{\mathcal {L}}(y|\theta _{i})P(\theta _{i})}}{\frac {Q(\theta _{i}|\theta ^{*})}{Q(\theta ^{*}|\theta _{i})}}\right),}" loading="lazy"></span>

wobei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9027196ecb178d598958555ea01c43157d83597c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.604ex; height:2.176ex;" alt="{\displaystyle {\mathcal {L}}}" loading="lazy"></span> die <a href="Likelihood" class="mw-redirect" title="Likelihood">Likelihood</a> der Daten ist, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P(\theta )}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P(\theta )}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/543ecac78af032493892f6608bff05542e961edb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.645ex; height:2.843ex;" alt="{\displaystyle P(\theta )}" loading="lazy"></span> die Prior-Wahrscheinlichkeitsdichte und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"></span> die (bedingte) Vorschlagsdichte.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<div class="sieheauch" role="navigation" style="font-style:italic;"><span class="sieheauch-text">Siehe auch</span>: <a href="Monte-Carlo-Simulation" title="Monte-Carlo-Simulation">Monte-Carlo-Simulation</a>, <a href="Monte-Carlo-Algorithmus" title="Monte-Carlo-Algorithmus">Monte-Carlo-Algorithmus</a> und <a href="MCMC-Verfahren" title="MCMC-Verfahren">MCMC-Verfahren</a></div>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noresize noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"><span class="mw-default-size" typeof="mw:File"><span title="Commons"></span></span></div><b><span class=""><a class="external text" href="https://commons.wikimedia.org/wiki/Category:Metropolis%E2%80%93Hastings_algorithm?uselang=de"><span lang="en">Commons</span>: Metropolis-Algorithmus</a></span></b> – Sammlung von Bildern, Videos und Audiodateien</div>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-:0-1"><span class="mw-cite-backlink">↑ <sup><a href="#cite_ref-:0_1-0">a</a></sup> <sup><a href="#cite_ref-:0_1-1">b</a></sup></span> <span class="reference-text">W. K. Hastings: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Monte Carlo sampling methods using Markov chains and their applications</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Biometrika</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>57</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 1. April 1970, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%221464-3510%22&key=cql">1464-3510</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>97–109</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1093/biomet%2F57.1.97">10.1093/biomet/57.1.97</a></span> (englisch, <a rel="nofollow" class="external text" href="https://academic.oup.com/biomet/article/57/1/97/284580">oup.com</a> [abgerufen am 4. Juli 2023]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Metropolis-Algorithmus&rft.atitle=Monte+Carlo+sampling+methods+using+Markov+chains+and+their+applications&rft.au=W.+K.+Hastings&rft.date=1970-04-01&rft.doi=10.1093%2Fbiomet%2F57.1.97&rft.genre=journal&rft.issn=1464-3510&rft.issue=1&rft.jtitle=Biometrika&rft.pages=97-109&rft.volume=57" style="display:none"> </span></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, Edward Teller: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Equation of State Calculations by Fast Computing Machines</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">The Journal of Chemical Physics</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>21</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>6</span>, 1. Juni 1953, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%220021-9606%22&key=cql">0021-9606</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1087–1092</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1063/1.1699114">10.1063/1.1699114</a></span> (englisch).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Metropolis-Algorithmus&rft.atitle=Equation+of+State+Calculations+by+Fast+Computing+Machines&rft.au=Nicholas+Metropolis%2C+Arianna+W.+Rosenbluth%2C+Marshall+N.+Rosenbluth%2C+...&rft.date=1953-06-01&rft.doi=10.1063%2F1.1699114&rft.genre=journal&rft.issn=0021-9606&rft.issue=6&rft.jtitle=The+Journal+of+Chemical+Physics&rft.pages=1087-1092&rft.volume=21" style="display:none"> </span></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">Vivekananda Roy: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Convergence Diagnostics for Markov Chain Monte Carlo</cite>. In: <cite class="lang" lang="en" dir="auto" style="font-style:italic">Annual Review of Statistics and Its Application</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>7</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 9. März 2020, <a href="Internationale_Standardnummer_f%C3%BCr_fortlaufende_Sammelwerke" title="Internationale Standardnummer für fortlaufende Sammelwerke">ISSN</a> <span style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://zdb-katalog.de/list.xhtml?t=iss%3D%222326-8298%22&key=cql">2326-8298</a></span>, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>387–412</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1146/annurev-statistics-031219-041300">10.1146/annurev-statistics-031219-041300</a></span> (englisch, <a rel="nofollow" class="external text" href="https://www.annualreviews.org/doi/10.1146/annurev-statistics-031219-041300">annualreviews.org</a> [abgerufen am 4. Juli 2023]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Metropolis-Algorithmus&rft.atitle=Convergence+Diagnostics+for+Markov+Chain+Monte+Carlo&rft.au=Vivekananda+Roy&rft.date=2020-03-09&rft.doi=10.1146%2Fannurev-statistics-031219-041300&rft.genre=journal&rft.issn=2326-8298&rft.issue=1&rft.jtitle=Annual+Review+of+Statistics+and+Its+Application&rft.pages=387-412&rft.volume=7" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2026-01-05" href="https://de.wikipedia.org/wiki/?title=Metropolis-Algorithmus&oldid=263069464">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>